1802F - The way home - CodeForces Solution

#include <bits/stdc++.h>

#define int long long
#define ull unsigned long long

using namespace std;

const int mod = 1e9 + 7;
const int mod_ = 1e9 + 6;
const int INF = 1e18 + 1;

void add(int & a, int b){
	b %= mod;
	a += b;
	if(a >= mod)
		a -= mod;
	return;
}

void sub(int & a, int b){
	b %= mod;
	a -= b;
	if(a < 0)
		a += mod;
	return;
}

int ask(int a,int b){
	cout<<"? "<<a<<' '<<b<<endl;
	int x;
	cin>>x;
	return x;
}

vector<vector<pair<int, int>>>graph;
vector<vector<int>>diss;
vector<bool>visited;

void djikstra(int source){
	set<pair<int, int>>s;
	diss[source][source] = 0;
	s.insert(make_pair(diss[source][source], source));
	while(!s.empty()){
		pair<int, int>p = *(s.begin());
		s.erase(s.begin());
		int dis = p.first; int node = p.second;
		visited[node] = true;
		for(auto edge : graph[node]){
			int next = edge.first; int w = edge.second;
			if(visited[next])
				continue;
			if(diss[source][next] <= dis + w)
				continue;
			if(diss[source][next] != INF)
				s.erase(make_pair(diss[source][next], next));
			s.insert(make_pair(dis + w, next));
			diss[source][next] = dis + w;
		}
	}
	fill(visited.begin(), visited.end(), false);
	return;
}

bool floyd_warshall(){
	int n = graph.size();
	for(int i = 0; i<n; i++)
		diss[i][i] = 0;
	for(int curr = 0; curr<n; curr++){
		for(auto edge : graph[curr]){
			int next = edge.first; int w = edge.second;
			diss[curr][next] = min(diss[curr][next], w);
		}
	}
	for(int k = 0; k<n; k++){
		for(int i = 0; i<n; i++){
			for(int j = 0; j<n; j++){
				if(diss[i][k] == INF || diss[k][j] == INF)
					continue;
				diss[i][j] = min(diss[i][j], diss[i][k] + diss[k][j]);
			}
		}
	}
	for(int i = 0; i<n; i++)
		if(diss[i][i] < 0)
			return true;
	return false;
}

bool compare(const vector<int> & a, const vector<int> & b){
	if(a[0] != b[0]) return a[0] < b[0];
	return a[1] < b[1];
}

void update(vector<vector<int>> & dp, int idx, int rev, int perfs, int coins){
	if(dp[idx][0] == -1){
		dp[idx][0] = perfs;
		dp[idx][1] = coins;
		return;
	}
	int prev_perfs = dp[idx][0];
	int prev_coins = dp[idx][1];
	int new_coins = coins;
	if(prev_perfs < perfs)
		prev_coins += (perfs-prev_perfs)*rev;
	if(perfs < prev_perfs)
		new_coins += (prev_perfs-perfs)*rev;
	if(prev_coins < new_coins)
		dp[idx][0] = perfs, dp[idx][1] = coins;
	return;
}

int32_t main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	#ifndef ONLINE_JUDGE
		freopen("input.txt" , "r" , stdin);
		freopen("output.txt" , "w" , stdout);
	#endif
	int t, n, m, p, u, v, w;
	cin >> t;
	while(t--){
		cin >> n >> m >> p;
		graph.resize(n);
		diss.assign(n, vector<int>(n, INF));
// 		visited.assign(n, false);
		vector<vector<int>>info(n, vector<int>(2, 0));
		vector<vector<int>>dp(n, vector<int>(2, -1));
		dp[0][0] = 0; dp[0][1] = p;
		for(int i = 0; i<n; i++){
			cin >> info[i][0];
			info[i][1] = i;
		}
		sort(info.begin(), info.end(), compare);
		for(int i = 0; i<m; i++){
			cin >> u >> v >> w;
			u--; v--;
			graph[u].push_back(make_pair(v, w));
		}
		floyd_warshall();
		for(int i = 1; i<n; i++){
			int rev = info[i][0];
			int city = info[i][1];
			if(city == n-1) continue;
			for(int j = i-1; j>=0; j--){
				int prev_rev = info[j][0];
				int prev_city = info[j][1];
				if(dp[prev_city][0] == -1 ||
				   diss[prev_city][city] == INF) continue;
				int extra_perfs = (max(diss[prev_city][city]-dp[prev_city][1],
									  0ll) + prev_rev - 1)/prev_rev;
				int perfs = dp[prev_city][0] + extra_perfs;
				int coins = dp[prev_city][1] + extra_perfs*prev_rev -
							diss[prev_city][city];
				update(dp, city ,rev, perfs, coins);
			}
		}
		int ans = INF;
		for(int i = 0; i<n; i++){
			int rev = info[i][0];
			int city = info[i][1];
			if(city == n-1 || diss[city][n-1] == INF || dp[city][0] == -1)
				continue;
			int extra_perfs = (max(diss[city][n-1]-dp[city][1], 0ll) +
							   rev - 1)/rev;
			ans = min(ans, extra_perfs+dp[city][0]);
		}
		cout << (ans == INF ? -1 : ans) << "\n";
		graph.clear();
		diss.clear();
// 		visited.clear();
	}
    return 0;
}